package problem97_Interleaving_String;

public class MySolution {
	public boolean isInterleave(String s1, String s2, String s3) {
		char[] s1Chars=s1.toCharArray();
		char[] s2Chars=s2.toCharArray();
		char[] s3Chars=s3.toCharArray();
		if(s1Chars.length+s2Chars.length!=s3Chars.length)	return false;
		boolean[][] dp=new boolean[s1Chars.length+1][s2Chars.length+1];
		dp[0][0]=true;
		for(int i=0;i<=s1Chars.length;i++){
			for(int j=0;j<=s2Chars.length;j++){
				if(i>0){
					dp[i][j]=dp[i-1][j]&&s1Chars[i-1]==s3Chars[i-1+j];
				}
				if(j>0){
					dp[i][j]|=dp[i][j-1]&&s2Chars[j-1]==s3Chars[j-1+i];
				}
			}
		}
		return dp[s1Chars.length][s2Chars.length];
    }
	
	public static void main(String[] args){
		System.out.println(new MySolution().isInterleave("a","", "c"));
	}
}
